package leetcode;
/**
 * 322.零钱兑换
 * 给定不同⾯额的硬币 coins 和⼀个总⾦额 amount。编写⼀个函数来计算可以凑成总⾦额所需的最少的硬币个数。
 * 如果没有任何⼀种硬币组合能组成总⾦额，返回 -1。
 * 你可以认为每种硬币的数量是⽆限的。
 * 示例 1：
 * 输⼊：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 * 输⼊：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 * 输⼊：coins = [1], amount = 0
 * 输出：0
 */
public class Num_322 {
    public int coinChange(int[] coins, int amount) {
        //dp[i][j]表示前i个硬币凑出j的最少数量
        int[][] dp = new int[coins.length+1][amount+1];
        //初始化
        //前i个硬币凑出0的数量就是0，dp[i][0] = 0
        //前0个硬币凑出j的值为-1
        for(int j=0; j<=amount; j++){
            dp[0][j] = -1;
        }
        //开始二重循环遍历
        for(int i=1; i<=coins.length; i++){
            for(int j=1; j<=amount; j++){
                //不选第i个的情况
                dp[i][j] = dp[i-1][j]; //有可能是-1
                //选择第i个的情况
                if(j>=coins[i-1] && dp[i][j-coins[i-1]] != -1){
                    // dp[i][j] = dp[i][j-coins[i-1]] + 1; 这是选了第i个的情况，需要比较两种情况哪种消耗硬币数量更少
                    //           前者是否存在            选出硬币消耗量少的那个                       直接选后者
                    dp[i][j] = dp[i-1][j]!=-1 ? Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1) : dp[i][j-coins[i-1]]+1;
                }
            }
        }
        return dp[coins.length][amount];
    }
}
